package sort;

/**
 * 快速排序
 */
public class FastSort {
	public static void main(String[] args) {
		int[] a = new int[]{0,2,22, 7, 4, 5, 1, 9, 3, 10,95,6};
		sort(a, 0, a.length - 1);
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i]+" ");
		}
	}
	private static int divide(int[] arr,int start,int end){
		int base = arr[end];
		while(start < end && arr[start]<base){
			start++;
		}
		if(start < end && arr[start] > base){
			int tmp = arr[start];
			arr[start] = arr[end];
			arr[end] = tmp;
		}
		while(start < end && arr[end] > base){
			end --;
		}
		if(start < end && arr[end] <base){
			int tmp = arr[start];
			arr[start] = arr[end];
			arr[end] = tmp;
		}
		return end;
	}
	private static void sort(int[] arr,int start,int end){
		if(arr.length == 0){
			return;
		}
		if(start > end){
			return;
		}

		int partition = divide(arr,start,end);
		sort(arr,start,partition-1);
		sort(arr,partition+1,end);
	}










/*
	public static int divide(int[] a, int start, int end) {
		int base = a[end];
		while (start < end) {
//从左往右遍历对比基准值
			while (start < end && a[start] <= base) start++;
//找到值后交换
			if (start < end) {
				int tmp = a[start];
				a[start] = a[end];
				a[end] = tmp;
// start++;
			}
//从右往左遍历对比基准值
			while (start < end && a[end] >= base) end--;
//找到之后交换
			if (start < end) {
				int tmp = a[start];
				a[start] = a[end];
				a[end] = tmp;
// end--;
			}
		}
		return end;
	}

	public static void sort(int[] a, int start, int end) {
		if (start > end) {
			return;
		} else {
			int partition = divide(a, start, end);
			sort(a, start, partition - 1);
			sort(a, partition + 1, end);
		}
	}

	public static void main(String[] args) {
		int[] a = new int[]{0,2,22, 7, 4, 5, 1, 9, 3, 10,95,6};
		sort(a, 0, a.length - 1);
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i]+" ");
		}
	}*/
}
